COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	(declare (special refuted d c p n) (fixsw t))
C00008 ENDMK
C⊗;
(declare (special refuted d c p n) (fixsw t))

(defun implies (premise conclusion)
;      (format t "Trying to prove that ~S implies ~s ~%"
;	       premise conclusion)
       (add-conjunction premise (opposite conclusion) () () () ()))

(defun opposite (f)
       (prog (O)
	     (setq o (car f))
	     (return
	      (cond ((eq o 'AND)
		     `(or ,(opposite (cadr f)) . ,(opposite (cddr f))))
		    ((eq o 'or)
		     `(and  ,(opposite (cadr f)) . ,(opposite (cddr f))))
		    ((eq O '+)
		     `(- . ,(cdr f)))
 		    ((eq O '-)
		     `(+ . ,(cdr f)))))))

(defun add-conjunction (f g d c p n)
       (prog (refuted)
;	     (format t "Expanding conjunction ~S by Rule 1 ~%"
;		     `(and  ,f . ,g))
	     (setq refuted ())
	     (expand f)
	     (expand g)
	     (cond 
	      (refuted
;	       (format t "Contradiction spotted~%")
	       (return t))
	      ((not (atom d))
	       (return (split (cadr (car d))
			      (cddr (car d))
			      (cdr d))))
	      (t 
	       ;(format t "Cannot refute ~S ~S ~S ~S ~%" d c p n)
	       (return ())))))

(defun split (f1 g1 d)
       (prog (f g)
;	     (format t "Case analysis on ~S (Rule 2)~%"
;		     `(or ,f . ,g))
	     (setq f (opposite f1))
	     (setq g (opposite g1))
	     (return
	      (and (add-conjunction f  g1 d c p n)
		   (add-conjunction f  g  d c p n)
		   (add-conjunction f1 g  d c p n)))))

(defun expand (f)
       (prog (o)
	     (setq o (car f))
	     (cond ((eq o 'and)
		    (cond ((member f d)
			   (setq refuted t))
			  ((member f c)
			   ())
			  (t (setq c `(,f . ,c))
			     (expand (cadr f))
			     (expand (cddr f)))))
		   ((eq o 'or)
		    (setq d (extend (opposite f) d c)))
		   ((eq o '+)
		    (setq p (extend (cdr f) p n)))
		   ((eq o '-)
		    (setq n (extend (cdr f) n p))))
	     (return ())))

(defun extend (f a b)
       (cond ((member f b)
	      (setq refuted t) a)
	     ((member f a) a)
	     (t `(,f . ,a))))

(defun try (m)
       (prog (a)
	     (setq a
		   '(
		     (- . a) (+ . a)
		     (+ . b) (or (- . b) . (- . b))
		     (+ . nothing) (or (+ . to-be) . (- . to-be))
		     (or (- . a) . (- . a)) (- . a)
		     (- . b) (or (+ . a) . (- . b))
		     (and (- . a) . (- . b))
		      (and (- . b) . (- . a))
	             (- . b) (or (- . a) . (and (+ . a) . (- . b)))
		     (or (- . a) . (or (- . b) . (+ . c)))
		      (or (- . b) . (or (- . a) . (+ . c)))
		     (or ( - . a) . (+ . b))
		      (or (and (+ . b) . (- . c))
			  . (or (- . a) . (+ . c)))
		     (and (or (- . a) . ( + . c)).
			  (or (- . b) . (+ . c)))
		      (or (and (- . a) . (- . b)) . (+ . c))))
	     l (cond ((> m 1)
		      (setq m (1- m))
		      (setq a (cddr a))
		      (go l)))
	     (return  (implies (car a)(cadr a)))))

(defun timed (k m)
       (prog ()
	     l (try m)
	     (cond ((> (setq k (1- k)) 0)
		    (go l)))))

(include "timer.lsp")
(timer timit
       (progn (timed  1000. 1.)
	      (timed 1000. 2)
	      (timed 1000. 3)
	      (timed 1000. 4)
	      (timed 1000. 5)
	      (timed 1000. 6)
	      (timed 1000. 7)
	      (timed 1000. 8)
	      (timed 1000. 9)
	      (timed 1000. 10.)))